const common = require('./base/common');
const Dump = require('./dataStruct/dump').Dump;

/**
 * 知乎上的一个网友提问：计算第K个最大的数字
 */
let findKBigNumber = function (arr, K) {
    if (K < 1 || K > arr.length) {
        return false;
    }

    /**
     * 交换数组的i和j元素
     * 
     * @param {*} i I 
     * @param {*} j J
     */
    function swap(arr, i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 这是一种基于快速排序思想的方法
     * 时间复杂度：O(n)
     */
    function quickSortAlog(arr) {
        let left = 0, right = arr.length;

        while (left < right) {
            let sentinel = arr[left],
                i = left + 1,
                j = right - 1;
            while (i < j) {
                if (arr[i] >= sentinel) {
                    i++;
                    continue;
                }
                if (arr[j] <= sentinel) {
                    j--;
                    continue;
                }
                swap(arr, i, j);
            }
            // 一定要注意，快排跳出循环的时候要比较一下
            if(arr[left] < arr[i]) {
                swap(arr, left, i);
            }
            if (i == K - 1) {
                return arr[i];
            } else if (i < K - 1) {
                left = i + 1;
            } else {
                right = i;
            }
        }
    }

    /**
     * 这是一种基于堆的方法
     * 时间复杂度：O(n * logK)
     */
    function dumpAlog(arr) {
        let dump = new Dump();
        for (let i = 0; i < arr.length; ++i) {
            if (dump.length < K) {
                dump.add(arr[i]);
                continue;
            }
            if (arr[i] > dump.peek) {
                dump.poll();
                dump.add(arr[i]);
            }
        }
        return dump.peek;
    }

    /**
     * 最简单的方法，直接排序然后取第K个最大的数字
     * 时间复杂度：O(n * logn)
     */
    function sortAlog(arr) {
        return arr.sort((a, b) => b - a)[K - 1];
    }

    /**
     * 冒泡法计算
     * 时间复杂度：O(K * n)
     */
    function bubbleAlog(arr) {
        for (let i = 0; i < K; ++i) {
            for (let j = arr.length - 2; j >= 0; --j) {
                if (arr[j + 1] > arr[j]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        return arr[K - 1];
    }

    return [sortAlog(arr.slice(0)), bubbleAlog(arr.slice(0)), dumpAlog(arr.slice(0)), quickSortAlog(arr.slice(0))]
}

common.testing([
    [[1, 2, 3, 4, 5, 6], 6],
    [[6, 5, 4, 3, 2, 2], 6],
    [[4, 6, 2, 5, 3, 1], 6],
    [[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 4, 5, 9, 2, 3, 0, 7, 8, 1, 6, 4, 0, 6, 2, 8, 6, 2, 0, 8, 9, 9, 8, 6, 2, 8, 0, 3, 4, 8, 2, 5, 3, 4, 2, 1, 1, 7, 0, 6, 7], 23]
])((x) => findKBigNumber(x[0], x[1]));

